package com.example.zz.example.datastructures.nowcoder;

import java.util.HashMap;
import java.util.HashSet;
import java.util.Stack;

/**
 * @author: zhuozhang6
 * @date: 2021/12/1
 * @email: zhuozhang6@iflytek.com
 * @Description:
 */
public class ListNodeOffer {
    public static void main(String[] args) {

        long a = 1L;
        long l = a % 10;

        //力扣，两数相加
        addTwoNumProblem();

        //删除链表中重复节点
        deleteDuplicationProblem();

        //复杂链表的复制
        randomListCloneProblem();

        //删除链表的节点
        deleteNodeProblem();

        //返回链表中倒数的k个节点
        findKthToTailProblem();

        //链表环入口
        entryNodeOfLoopProblem();

        //两个链表的第一个公共节点
        findFirstCommonProblem();

        //合并两个链表
        mergeListProblem();

        //链表翻转
        reverseListProblem();

        //从尾到头打印链表题目
        printListFormTailToHeadProblem();
    }

    private static void addTwoNumProblem() {
        System.out.println("力扣：0");
        ListNode head = new ListNode(2);
        ListNode head2 = new ListNode(4);
        ListNode head3 = new ListNode(3);

        ListNode head4 = new ListNode(5);
        ListNode head5 = new ListNode(6);
        ListNode head6 = new ListNode(4);
        head.next = head2;
        head2.next = head3;

        head4.next = head5;
        head5.next = head6;

        ListNode listNode = addTwoNumbers(head, head4);
        System.out.println("力扣：" + listNode.val);
    }

    public static ListNode addTwoNumbers(ListNode l3, ListNode l4) {
        ListNode l1 = l3;
        ListNode l2 = l4;
        System.out.println("力扣：1");
        Stack<Integer> a = new Stack<>();
        System.out.println("力扣：2");
        while (l1 != null) {
            int val = l1.val;
            a.push(val);
            l1 = l1.next;
        }
        System.out.println("力扣：3");
        int n1 = 0;
        int k = 1;
        while (a.size() > 0 && a.peek() != null) {
            n1 = a.pop() * k + n1;
            k = k * 10;
        }
        System.out.println("力扣：n1 = " + n1);


        Stack<Integer> b = new Stack<>();
        while (l2 != null) {
            b.push(l2.val);
            l2 = l2.next;
        }
        int n2 = 0;
        int j = 1;
        while (b.size() > 0 && b.peek() != null) {
            n2 = b.pop() * j + n2;
            j = j * 10;
        }
        System.out.println("力扣：n2 = " + n2);
        int n3 = n1 + n2;
        System.out.println("两数相加后效果：" + n3);
        ListNode ln = null;
        Stack<Integer> d = new Stack<>();
        while (n3 > 0) {
            d.push(n3 % 10);
            n3 = n3 / 10;
        }

        while (d.size() > 0 && d.peek() != null) {
            ln = new ListNode(d.pop());
        }

        while (d.size() > 0 && d.peek() != null) {
            ln.next = new ListNode(d.pop());
            ln = ln.next;
        }
        return ln;
    }

    private static void deleteDuplicationProblem() {
        ListNode head = new ListNode(1);
        ListNode head2 = new ListNode(2);
        ListNode head3 = new ListNode(3);
        ListNode head4 = new ListNode(3);
        ListNode head5 = new ListNode(5);
        head.next = head2;
        head2.next = head3;
        head3.next = head4;
        head4.next = head5;
        //删除重复节点，保留其中一个
        ListNode list = deleteDuplication(head);
        System.out.println("删除重复节点，只保留一个：");
        show(list);


        ListNode p = new ListNode(1);
        ListNode p2 = new ListNode(2);
        ListNode p3 = new ListNode(3);
        ListNode p4 = new ListNode(3);
        ListNode p5 = new ListNode(5);
        p.next = p2;
        p2.next = p3;
        p3.next = p4;
        p4.next = p5;
        ListNode listAll = deleteDuplicationAll(p);
        System.out.println("删除重复节点，重复的都删除：");
        show(listAll);
    }

    private static ListNode deleteDuplicationAll(ListNode head) {
        // 1、当输入为空或者不存在时，直接返回
        // 2、当前节点与下一节点不同时，当前是有效节点保留
        // 3、当前节点与下一节点相同时，while循环跳过相同的连续段
        // 4、最后一个相同的节点与下一个节点是不同的，会被保留
        // 5、循环2到5，遍历所有节点
        if (head == null) {
            return head;
        }
        ListNode temp = new ListNode(-1);       //用来记录头结点，返回结果
        temp.next = head;
        while (temp.next != null && temp.next.next != null) {
            if (temp.next.val == temp.next.next.val) {
                int k = temp.next.val;
                while (temp.next.val == k) {
                    temp.next = temp.next.next;
                }
            } else {
                temp = temp.next;
            }
        }
        return head;
    }

    private static ListNode deleteDuplication(ListNode head) {
        // 方案：循环链表，将符合规则的节点放入新链表
        // 1、当输入为空或者不存在时，直接返回
        // 2、双链表，一个链表进行循环，一个链表进行存储
        // 3、head链表进行循环，比较当前节点和下一个节点：如果两者不同，当前节点就连接到temp链表上，指针后移；如果相同，当前节点不连接到temp上，指针后移
        // 4、重复进行第3步
        // 5、所以相同的相连节点，前面的节点都不会被添加到temp中
        if (head == null) {
            return head;
        }
        ListNode temp = new ListNode(-1);
        ListNode tempNew = temp;
        while (head != null) {
            if (head.next != null && head.val != head.next.val) {
                temp.next = head;
                temp = temp.next;
            }
            head = head.next;
        }
        return tempNew.next;
    }

    public ListNode deleteDuplications(ListNode pHead) {
        // 1、当输入为空或者不存在时，结束
        // 2、当前节点与下一节点不同时，当前是有效节点保留
        // 3、当前节点与下一节点相同时，跳过相同的连续段
        if (pHead == null) {
            return pHead;
        }
        // 创建哑节点
        ListNode dummy = new ListNode(-1);
        dummy.next = pHead;
        ListNode cur = dummy;
        while (cur.next != null && cur.next.next != null) {
            if (cur.next.val == cur.next.next.val) {
                int x = cur.next.val;
                while (cur.next != null && cur.next.val == x) {
                    cur.next = cur.next.next;
                }
            } else {
                cur = cur.next;
            }
        }
        return dummy.next;
    }

    private static void randomListCloneProblem() {
        RandomListNode head = new RandomListNode(1);
        RandomListNode head2 = new RandomListNode(2);
        RandomListNode head3 = new RandomListNode(3);
        RandomListNode head4 = new RandomListNode(4);
        RandomListNode head5 = new RandomListNode(5);
        head.next = head2;
        head2.next = head3;
        head3.next = head4;
        head4.next = head5;

        head.random = head3;
        head2.random = head5;
        head4.random = head2;

        RandomListNode clonedList = randomListClone(head);
        int val = clonedList.val;
    }

    private static RandomListNode randomListClone(RandomListNode head) {
        //法一：hash表法，遍历一遍原链表的同时复制构建到一份新链表，同时将新老节点存到HashMap中；第二遍遍历时，将random属性再次赋值  时间 O(n) 空间 O(n)
        RandomListNode temp = head;//原链表备份
        RandomListNode newNode = new RandomListNode(-1);//生成新链表
        RandomListNode newTemp = newNode;//新链表备份
        HashMap<RandomListNode, RandomListNode> map = new HashMap<>();
        //第一遍循环，构建链表并赋值val属性
        while (temp != null) {
            RandomListNode randomListNode = new RandomListNode(temp.val);
            map.put(temp, randomListNode);
            newTemp.next = randomListNode;
            newTemp = newTemp.next;
            temp = temp.next;
        }
        //第二遍循环，从map中取值，进行ramdom赋值
        while (head != null) {
            RandomListNode randomListNode = map.get(head);
            randomListNode.random = head.random;
            head = head.next;
        }
        newNode = newNode.next;
        return newNode;

        //法二：原地解法 时间 O(n) 空间 O(1)
//        if(head == null) return head;
//        // 1.将拷贝节点放到原节点后面，例如1->2->3这样的链表就变成了这样1->1'->2->2'->3->3'
//        for (RandomListNode node = head, copy = null; node != null; node = node.next.next) {
//            copy = new RandomListNode(node.val);
//            copy.next = node.next;
//            node.next = copy;
//        }
//        // 2.把拷贝节点的random指针安排上
//        for (RandomListNode node = head; node != null; node = node.next.next) {
//            if (node.random != null) {
//                node.next.random = node.random.next;
//            }
//        }
//        // 3.分离拷贝节点和原节点，变成1->2->3和1'->2'->3'两个链表，后者就是答案
//        RandomListNode newHead = head.next;
//        for (RandomListNode node = head, temp = null; node != null && node.next != null;) {
//            temp = node.next;
//            node.next = temp.next;
//            node = temp;
//        }
//        return newHead;

    }

    private static void deleteNodeProblem() {
        ListNode head = new ListNode(2);
        ListNode head2 = new ListNode(5);
        ListNode head3 = new ListNode(1);
        ListNode head4 = new ListNode(9);
        head.next = head2;
        head2.next = head3;
        head3.next = head4;
        int k = 5;
        ListNode listNode = deleteNode(head, k);

        System.out.println("删除链表中值：" + k + "的节点");
        show(listNode);
    }

    private static ListNode deleteNode(ListNode head, int val) {
        if (head == null) {
            return head;
        }
        ListNode temp = head;
        if (head.val == val) {
            head = head.next;
            return head;
        }
        while (temp.next != null) {
            if (temp.next.val == val) {
                temp.next = temp.next.next;
                break;
            }
        }
        return head;
    }

    private static void findKthToTailProblem() {
        ListNode head = new ListNode(1);
        ListNode head2 = new ListNode(2);
        ListNode head3 = new ListNode(3);
        ListNode head4 = new ListNode(4);
        ListNode head5 = new ListNode(5);
        head.next = head2;
        head2.next = head3;
        head3.next = head4;
        head4.next = head5;

        int k = 2;
        ListNode listNode = findKthToTail(head, k);

        System.out.println("倒数第k(=" + k + ")个节点");
        show(listNode);
    }

    private static ListNode findKthToTail(ListNode head, int k) {

        //法一：递归法
        kk = k;
        findKthToTailTemp(head);
        return result;

        //法二：压栈出栈重组法

        //法三：双链表法

//        return null;
    }

    private static int num = 0;
    private static int kk = 0;
    private static ListNode result;

    private static void findKthToTailTemp(ListNode head) {
        if (head == null) {
            return;
        }
        findKthToTailTemp(head.next);
        ++num;
        if (num == kk) {
            result = head;
        }
    }

    private static void entryNodeOfLoopProblem() {
        ListNode list1 = new ListNode(1);
        ListNode head2 = new ListNode(2);
        ListNode head3 = new ListNode(3);
        ListNode head4 = new ListNode(4);
        ListNode head5 = new ListNode(5);
        list1.next = head2;
        head2.next = head3;
        head3.next = head4;
        head4.next = head5;
        head5.next = head3;
        ListNode listNode = entryNodeOfLoop(list1);
        System.out.println("环的入口： " + listNode.val);
    }

    private static ListNode entryNodeOfLoop(ListNode head) {
        HashSet<ListNode> hashSet = new HashSet<>();
        ListNode result = null;
        while (head != null) {
            if (hashSet.contains(head)) {
                result = head;
                break;
            }
            hashSet.add(head);
            head = head.next;
        }
        return result;
    }

    private static void findFirstCommonProblem() {
        ListNode list1 = new ListNode(1);
        ListNode head2 = new ListNode(2);
        ListNode head3 = new ListNode(3);
        ListNode head6 = new ListNode(6);
        ListNode head7 = new ListNode(7);
        list1.next = head2;
        head2.next = head3;
        head3.next = head6;
        head6.next = head7;

        ListNode list2 = new ListNode(4);
        ListNode head5 = new ListNode(5);
        list2.next = head5;
        head5.next = head6;
        head6.next = head7;

        ListNode firstCommon = findFirstCommon(list1, list2);
        System.out.println("第一个公共节点： " + firstCommon.val);
    }

    private static ListNode findFirstCommon(ListNode list1, ListNode list2) {
        ListNode list11 = list1;
        ListNode list22 = list2;
        while (list1 != list2) {
            list1 = list1 == null ? list22 : list1.next;
            list2 = list2 == null ? list11 : list2.next;
        }
        return list1;
    }


    private static void mergeListProblem() {
        ListNode list1 = new ListNode(1);
        ListNode head2 = new ListNode(3);
        ListNode head3 = new ListNode(5);
        list1.next = head2;
        head2.next = head3;

        ListNode list2 = new ListNode(2);
        ListNode head4 = new ListNode(4);
        ListNode head5 = new ListNode(6);
        list2.next = head4;
        head4.next = head5;

        ListNode merge = merge(list1, list2);
        System.out.println("合并列表");
        show(merge);
    }

    private static ListNode merge(ListNode list1, ListNode list2) {
        if (list1 == null) {
            return list2;
        }
        if (list2 == null) {
            return list1;
        }
        if (list1.val < list2.val) {
            list1.next = merge(list1.next, list2);
            return list1;
        } else {
            list2.next = merge(list1, list2.next);
            return list2;
        }
    }

    private static void reverseListProblem() {
        ListNode head1 = new ListNode(1);
        ListNode head2 = new ListNode(2);
        ListNode head3 = new ListNode(3);
        ListNode head4 = new ListNode(4);

        head1.next = head2;
        head2.next = head3;
        head3.next = head4;

        ListNode listNode = reverseList(head1);
        System.out.println("翻转链表");
        show(listNode);
    }

    private static ListNode reverseList(ListNode head) {

        //法一：使用栈，取出链表存到栈中，新建两个链表，一个用来循环一个用来返回，进入循环组成新链表
//        Stack<ListNode> stack = new Stack<>();
//        while (head != null) {
//            stack.push(head);
//            head = head.next;
//        }
//        if (stack.isEmpty()) {
//            return null;
//        }
//        ListNode node = stack.pop();
//        ListNode result = node;
//        while (!stack.isEmpty()) {
//            ListNode pop = stack.pop();
//            node.next = pop;
//            node = node.next;
//        }
//        node.next = null;
//        return result;

        //法二：使用递归。递归三要素，终止条件、递处理、归处理。由于翻转可以递的时候进行翻转，也可以归的时候进行组合，所有有多种实现方式
//        return reverseListInt(head, null);
        return reverseListInt2(head);

        //法三：双链表法，逐个取出组成新链表，方案类似交换两个值，使用临时链表保存
//        ListNode result = null;
//        ListNode temp = null;
//        while (head != null) {
//            temp = head.next;
//            head.next = result;
//            result = head;
//            head = temp;
//        }
//        return result;
    }

    //递归法一，递的过程中进行数据处理，处理类似法三
    private static ListNode reverseListInt(ListNode head, ListNode result) {
        if (head == null) {
            return result;
        }
        ListNode temp = head.next;
        head.next = result;
        result = head;
        head = temp;

        return reverseListInt(head, result);
    }

    //递归法二，归的过程中进行数据处理
    private static ListNode reverseListInt2(ListNode head) {
        if (head == null || head.next == null) {
            return head;
        }
        ListNode next = head.next;//保存当前节点的下一节点
        ListNode reverse = reverseListInt2(next);
        next.next = head;
        head.next = null;
        return reverse;
    }

    private static void printListFormTailToHeadProblem() {
        ListNode head1 = new ListNode(1);
        ListNode head2 = new ListNode(2);
        ListNode head3 = new ListNode(3);
        ListNode head4 = new ListNode(4);

        head1.next = head2;
        head2.next = head3;
        head3.next = head4;
        System.out.println("链表倒序打印");
        printListFormTailToHead(head1);
    }

    //从尾到头打印链表
    public static void printListFormTailToHead(ListNode listNode) {
        if (listNode == null) {
            return;
        }
        printListFormTailToHead(listNode.next);
        System.out.printf(listNode.val + " ");
    }

    static class ListNode {
        public int val;
        public ListNode next = null;

        public ListNode(int val) {
            this.val = val;
        }
    }

    static class RandomListNode {
        public int val;
        public RandomListNode next = null;
        public RandomListNode random = null;

        public RandomListNode(int val) {
            this.val = val;
        }

    }

    // 直观打印列表方法
    public static void show(ListNode head) {
        if (head == null) {
            System.out.println("EMPTY LIST!");
            return;
        }
        ListNode currNode = head;
        while (currNode.next != null) {
            System.out.print(currNode.val);
            System.out.print("->");
            currNode = currNode.next;
        }
        System.out.print(currNode.val);
        System.out.println();
    }
}
